/*****************************************************************************
*                                                                            *
*  ex-1.c                                                                    *
*  ======                                                                    *
*                                                                            *
*  Description: Illustrates using a graph (see Chapter 11).                  *
*                                                                            *
*****************************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "graph.h"
#include "list.h"
#include "set.h"

/*****************************************************************************
*                                                                            *
*  Define the size of strings.                                               *
*                                                                            *
*****************************************************************************/

#define            STRSIZ                2

/*****************************************************************************
*                                                                            *
*  ------------------------------ print_graph -----------------------------  *
*                                                                            *
*****************************************************************************/

static void print_graph(const Graph *graph) {

Set                *adjacent;

ListElmt           *element,
                   *member;

int                i,
                   j;

/*****************************************************************************
*                                                                            *
*  Display the graph.                                                        *
*                                                                            *
*****************************************************************************/

fprintf(stdout, "Vertices=%d, edges=%d\n", graph_vcount(graph), graph_ecount
   (graph));

i = 0;
element = list_head(&graph_adjlists(graph));

while (i < list_size(&graph_adjlists(graph))) {

   fprintf(stdout, "graph[%03d]=%s: ", i, (char *)((AdjList *)list_data(
      element))->vertex);

   j = 0;
   adjacent = &((AdjList *)list_data(element))->adjacent;
   member = list_head(adjacent);

   while (j < set_size(adjacent)) {

      if (j > 0) fprintf(stdout, ", ");
      fprintf(stdout, "%s", (char *)list_data(member));
      member = list_next(member);
      j++;

   }

   i++;
   fprintf(stdout, "\n");
   element = list_next(element);

}

return;

}

/*****************************************************************************
*                                                                            *
*  ------------------------------- match_str ------------------------------  *
*                                                                            *
*****************************************************************************/

static int match_str(const void *str1, const void *str2) {

/*****************************************************************************
*                                                                            *
*  Determine whether two strings match.                                      *
*                                                                            *
*****************************************************************************/

return !strcmp((const char *)str1, (const char *)str2);

}

/*****************************************************************************
*                                                                            *
*  --------------------------------- main ---------------------------------  *
*                                                                            *
*****************************************************************************/

int main(int argc, char **argv) {

Graph              graph;

AdjList            *adjlist;

ListElmt           *element;

char               *data,
                   data1[STRSIZ],
                   *data2;

int                retval,
                   size,
                   i;

/*****************************************************************************
*                                                                            *
*  Initialize the graph.                                                     *
*                                                                            *
*****************************************************************************/

graph_init(&graph, match_str, free);

/*****************************************************************************
*                                                                            *
*  Perform some graph operations.                                            *
*                                                                            *
*****************************************************************************/

if ((data = (char *)malloc(STRSIZ)) == NULL)
   return 1;

strcpy(data, "a");
fprintf(stdout, "Inserting vertex %s\n", data);

if (graph_ins_vertex(&graph, data) != 0)
   return 1;

if ((data = (char *)malloc(STRSIZ)) == NULL)
   return 1;

strcpy(data, "b");
fprintf(stdout, "Inserting vertex %s\n", data);

if (graph_ins_vertex(&graph, data) != 0)
   return 1;

if ((data = (char *)malloc(STRSIZ)) == NULL)
   return 1;

strcpy(data, "c");
fprintf(stdout, "Inserting vertex %s\n", data);

if (graph_ins_vertex(&graph, data) != 0)
   return 1;

if ((data = (char *)malloc(STRSIZ)) == NULL)
   return 1;

strcpy(data, "d");
fprintf(stdout, "Inserting vertex %s\n", data);

if (graph_ins_vertex(&graph, data) != 0)
   return 1;

if ((data = (char *)malloc(STRSIZ)) == NULL)
   return 1;

strcpy(data, "e");
fprintf(stdout, "Inserting vertex %s\n", data);

if (graph_ins_vertex(&graph, data) != 0)
   return 1;

print_graph(&graph);

if ((data2 = (char *)malloc(STRSIZ)) == NULL)
   return 1;

strcpy(data1, "a");
strcpy(data2, "b");
fprintf(stdout, "Inserting edge %s to %s\n", data1, data2);

if (graph_ins_edge(&graph, data1, data2) != 0)
   return 1;

print_graph(&graph);

if ((data2 = (char *)malloc(STRSIZ)) == NULL)
   return 1;

strcpy(data1, "a");
strcpy(data2, "c");
fprintf(stdout, "Inserting edge %s to %s\n", data1, data2);

if (graph_ins_edge(&graph, data1, data2) != 0)
   return 1;

print_graph(&graph);

if ((data2 = (char *)malloc(STRSIZ)) == NULL)
   return 1;

strcpy(data1, "b");
strcpy(data2, "c");
fprintf(stdout, "Inserting edge %s to %s\n", data1, data2);

if (graph_ins_edge(&graph, data1, data2) != 0)
   return 1;

print_graph(&graph);

if ((data2 = (char *)malloc(STRSIZ)) == NULL)
   return 1;

strcpy(data1, "b");
strcpy(data2, "d");
fprintf(stdout, "Inserting edge %s to %s\n", data1, data2);

if (graph_ins_edge(&graph, data1, data2) != 0)
   return 1;

print_graph(&graph);

if ((data2 = (char *)malloc(STRSIZ)) == NULL)
   return 1;

strcpy(data1, "c");
strcpy(data2, "b");
fprintf(stdout, "Inserting edge %s to %s\n", data1, data2);

if (graph_ins_edge(&graph, data1, data2) != 0)
   return 1;

print_graph(&graph);

if ((data2 = (char *)malloc(STRSIZ)) == NULL)
   return 1;

strcpy(data1, "c");
strcpy(data2, "c");
fprintf(stdout, "Inserting edge %s to %s\n", data1, data2);

if (graph_ins_edge(&graph, data1, data2) != 0)
   return 1;

print_graph(&graph);

if ((data2 = (char *)malloc(STRSIZ)) == NULL)
   return 1;

strcpy(data1, "c");
strcpy(data2, "d");
fprintf(stdout, "Inserting edge %s to %s\n", data1, data2);

if (graph_ins_edge(&graph, data1, data2) != 0)
   return 1;

print_graph(&graph);

if ((data2 = (char *)malloc(STRSIZ)) == NULL)
   return 1;

strcpy(data1, "d");
strcpy(data2, "a");
fprintf(stdout, "Inserting edge %s to %s\n", data1, data2);

if (graph_ins_edge(&graph, data1, data2) != 0)
   return 1;

print_graph(&graph);

if ((data2 = (char *)malloc(STRSIZ)) == NULL)
   return 1;

strcpy(data1, "e");
strcpy(data2, "c");
fprintf(stdout, "Inserting edge %s to %s\n", data1, data2);

if (graph_ins_edge(&graph, data1, data2) != 0)
   return 1;

print_graph(&graph);

if ((data2 = (char *)malloc(STRSIZ)) == NULL)
   return 1;

strcpy(data1, "e");
strcpy(data2, "d");
fprintf(stdout, "Inserting edge %s to %s\n", data1, data2);

if (graph_ins_edge(&graph, data1, data2) != 0)
   return 1;

print_graph(&graph);

if ((data2 = (char *)malloc(STRSIZ)) == NULL)
   return 1;

strcpy(data1, "a");
strcpy(data2, "c");
data = data2;

fprintf(stdout, "Removing edge %s to %s\n", data1, data2);

if (graph_rem_edge(&graph, data1, (void **)&data) != 0)
   return 1;

free(data);
print_graph(&graph);

strcpy(data1, "c");
strcpy(data2, "c");
data = data2;

fprintf(stdout, "Removing edge %s to %s\n", data1, data2);

if (graph_rem_edge(&graph, data1, (void **)&data) != 0)
   return 1;

free(data);
print_graph(&graph);

strcpy(data1, "e");
strcpy(data2, "c");
data = data2;

fprintf(stdout, "Removing edge %s to %s\n", data1, data2);

if (graph_rem_edge(&graph, data1, (void **)&data) != 0)
   return 1;

free(data);
print_graph(&graph);

strcpy(data1, "a");
strcpy(data2, "b");
data = data2;

fprintf(stdout, "Removing edge %s to %s\n", data1, data2);

if (graph_rem_edge(&graph, data1, (void **)&data) != 0)
   return 1;

free(data);
print_graph(&graph);

strcpy(data1, "d");
strcpy(data2, "a");
data = data2;

fprintf(stdout, "Removing edge %s to %s\n", data1, data2);

if (graph_rem_edge(&graph, data1, (void **)&data) != 0)
   return 1;

free(data);
print_graph(&graph);

free(data2);

strcpy(data1, "a");
data = data1;

fprintf(stdout, "Removing vertex %s\n", data1);

if (graph_rem_vertex(&graph, (void **)&data) != 0)
   return 1;

free(data);
print_graph(&graph);

if ((data2 = (char *)malloc(STRSIZ)) == NULL)
   return 1;

strcpy(data1, "f");
strcpy(data2, "a");

retval = graph_ins_edge(&graph, data1, data2);
fprintf(stdout,"Inserting an invalid edge from %s to %s...Value=%d (-1=OK)\n",
   data1, data2, retval);

if (retval != 0)
   free(data2);

print_graph(&graph);

if ((data2 = (char *)malloc(STRSIZ)) == NULL)
   return 1;

strcpy(data1, "c");
strcpy(data2, "b");

retval = graph_ins_edge(&graph, data1, data2);
fprintf(stdout,"Inserting an existing edge from %s to %s...Value=%d (1=OK)\n",
   data1, data2, retval);

if (retval != 0)
   free(data2);

print_graph(&graph);

if ((data2 = (char *)malloc(STRSIZ)) == NULL)
   return 1;

strcpy(data1, "f");
strcpy(data2, "a");
data = data2;

retval = graph_rem_edge(&graph, data1, (void **)&data);
fprintf(stdout, "Removing an invalid edge from %s to %s...Value=%d (-1=OK)\n",
   data1, data2, retval);

if (retval == 0)
   free(data);

free(data2);
print_graph(&graph);

if ((data2 = (char *)malloc(STRSIZ)) == NULL)
   return 1;

strcpy(data1, "c");
strcpy(data2, "e");
data = data2;

retval = graph_rem_edge(&graph, data1, (void **)&data);
fprintf(stdout, "Removing an invalid edge from %s to %s...Value=%d (-1=OK)\n",
   data1, data2, retval);

if (retval == 0)
   free(data);

free(data2);
print_graph(&graph);

if ((data2 = (char *)malloc(STRSIZ)) == NULL)
   return 1;

strcpy(data2, "c");

retval = graph_ins_vertex(&graph, data2);
fprintf(stdout, "Inserting an existing vertex %s...Value=%d (1=OK)\n", data1,
   retval);

if (retval != 0)
   free(data2);

print_graph(&graph);

if ((data2 = (char *)malloc(STRSIZ)) == NULL)
   return 1;

strcpy(data1, "b");
strcpy(data2, "d");

retval = graph_is_adjacent(&graph, data1, data2);
fprintf(stdout, "Testing graph_is_adjacent (%s, %s)...Value=%d (1=OK)\n",
   data1, data2, retval);

strcpy(data1, "a");
strcpy(data2, "e");

retval = graph_is_adjacent(&graph, data1, data2);
fprintf(stdout, "Testing graph_is_adjacent (%s, %s)...Value=%d (0=OK)\n",
   data1, data2, retval);

strcpy(data1, "e");
strcpy(data2, "d");

retval = graph_is_adjacent(&graph, data1, data2);
fprintf(stdout, "Testing graph_is_adjacent (%s, %s)...Value=%d (1=OK)\n",
   data1, data2, retval);

strcpy(data1, "c");
strcpy(data2, "a");

retval = graph_is_adjacent(&graph, data1, data2);
fprintf(stdout, "Testing graph_is_adjacent (%s, %s)...Value=%d (0=OK)\n",
   data1, data2, retval);

free(data2);

strcpy(data1, "c");

if (graph_adjlist(&graph, data1, &adjlist) != 0)
   return 1;

fprintf(stdout, "Vertices adjacent to %s: ", data1);

i = 0;
size = set_size(&adjlist->adjacent);
element = list_head(&adjlist->adjacent);

while (i < size) {

   i++;
   if (i > 1) fprintf(stdout, ", ");
   fprintf(stdout, "%s", (char *)list_data(element));
   element = list_next(element);

}

fprintf(stdout, "\n");

/*****************************************************************************
*                                                                            *
*  Destroy the graph.                                                        *
*                                                                            *
*****************************************************************************/

fprintf(stdout, "Destroying the graph\n");
graph_destroy(&graph);

return 0;

}
